import java.util.Iterator;


public class CircularArraySequence<T> implements Sequence<T> {

	protected Object[] array;
	protected int head, last;
	
	@SuppressWarnings("unchecked")
	public CircularArraySequence(int size) {
		array = (T[]) new Object[size];
		head = 0;
		last = 0;
	;}
	
	public CircularArraySequence(CircularArraySequence<T> seq) {
		this(seq.array.length);
		for(int i = 0; i < array.length; i++)
			this.array[i] = seq.array[i];
		this.head = seq.head;
		this.last = seq.last;
	}
	
	@Override
	public T head() {
		T firstElement = peekHead();
		if(isEmpty() == true)
			return null;
		for(int i = 0; i < length(); i++)
			array[i] = array[i+1];
		for(int i = length(); i < array.length; i++)
			array[i] = null;
		return firstElement;
	}

	@Override
	public T last() {
		T lastElement = peekLast();
		if(isEmpty() == true)
			return null;
		array[last] = null;
		decLastPtr();
		return lastElement;
	}

	@Override
	public Sequence<T> front() {
		CircularArraySequence<T> seq = new CircularArraySequence<T>(this);
		if(seq.isEmpty())
			return seq;
		else {
			seq.array[last] = null;
			seq.decLastPtr();
			return seq;
		}
	}

	@Override
	public Sequence<T> tail() {
		CircularArraySequence<T> seq = new CircularArraySequence<T>(this);
		if(seq.isEmpty())
			return seq;
		else {
			seq.array[head] = null;
			seq.incHeadPtr();
			return seq;
		}
	}

	@Override
	public Sequence<T> concat(Sequence<T> seq) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean contains(Sequence<T> subseq) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean contains(T element) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void append(T element) {
		if(array.length == length())
			regrow();
		if(isEmpty())
			array[last] = element;
		else {
			incLastPtr();
			array[last] = element;
		}
	}

	@Override
	public void prepend(T element) {
		if(array.length == length())
			regrow();
		if(isEmpty())
			array[head] = element;
		else {
			decHeadPtr();
			array[head] = element;
		}
	}

	@Override
	public boolean isEmpty() {
		for(int i = 0; i < array.length; i++) {
			if(array[i] != null)
				return false;
		}
		return true;
	}

	@SuppressWarnings("unchecked")
	@Override
	public T peekHead() {
		if(isEmpty() == true)
			return null;
		else
			return (T) array[head];
	}

	@SuppressWarnings("unchecked")
	@Override
	public T peekLast() {
		if(isEmpty() == true)
			return null;
		else
			return (T) array[last];
	}

	@Override
	public boolean equals(Sequence<T> seq) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int length() {
		int count = 0;
		if(isEmpty() == false){
			for(int i = 0; i < array.length; i++){
				if(array[i] != null)
					count++;
			}
			return count;
		}
		return 0;
	}

	@Override
	public Iterator<T> iterator() {
		SequenceIterator<T> it = new SequenceIterator<T>(this);
		return it;
	}
	
	public String toString() {
		String str = "";
		if(isEmpty() == true)
			return "";
		for(int i = head; i < array.length; i++) {
			if(array[i] != null)
				str += (String) array[i];
		}
		if(head != 0) {
			for(int j = 0; j <= last; j++)
				str += (String) array[j];
		}
		return str;
	}
	
	@SuppressWarnings("unchecked")
	public void regrow() {
		int cnt = 0;
		Object[] newArray = (T[]) new Object[array.length*2];
		for(int j = 0, i = head; i < array.length; j++, i++) {
			if(array[i] != null)
				newArray[j] = array[i];
			cnt = j;
		}
		if(head != 0) {
			for(int j = cnt+1, i = 0; i <= last; j++, i++)
				if(newArray[j] == null)
					newArray[j] = array[i];
		}
		head = 0;
		last = length() - 1;
		array = newArray;
	}
	
	public void incHeadPtr() {
		if(head == array.length-1)
			head = 0;
		else
			head += 1;
	}
	
	public void decHeadPtr() {
		if(head == 0)
			head = array.length-1;
		else
			head -= 1;
	}
	
	public void incLastPtr() {
		if(last == array.length-1)
			last = 0;
		else
			last += 1;
	}
	
	public void decLastPtr() {
		if(last == 0)
			last = array.length-1;
		else
			last -= 1;
	}

}
